ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpb/trains/main.cpp

   1 #include <iostream>
   2 #include <string>
   3 #include <map>
   4 #include <set>
   5 #include <vector>
   6 #include <list>
   7 #include <cassert>
   8 #include <cstdlib>
   9
  10 using namespace std;
  11
  12 #define forsn(i, s, n)  for (int i = (s); i < (n); i++)
  13 #define forn(i, n)      forsn (i, 0, n)
  14 #define forall(x, s)    for (typeof((s).begin()) x = (s).begin(); x != (s).end(); x++)
  15 #define dforall(x, s)   for (typeof((s).rbegin()) x = (s).rbegin(); x != (s).rend(); x++)
  16
  17 typedef int Id; // station id
  18 typedef int Time;
  19 typedef pair<Id, Time> Nodo;
  20
  21 struct Edge {
  22         Nodo dest;
  23         Time cost;
  24 };
  25 typedef vector<Edge> Ady;
  26 typedef map<Nodo, Ady> Grafo;
  27
  28 typedef map<string, pair<Id, set<Time> > > Stations;
  29
  30 // map<Nodo, Ady>::iterator
  31 #define _nodo           first
  32 #define _ady            second
  33
  34 // Stations::iterator
  35 #define _info           second
  36
  37 // pair<Id, set<Time> >
  38 #define _id             first
  39 #define _timeset        second
  40
  41 // Nodo
  42 #define _time           second
  43
  44 #define HOUR 60
  45 #define DAY (24 * HOUR)
  46
  47 Id inline register_station(Stations& stations, const string& station_name, Time time) {
  48         Stations::iterator it(stations.find(station_name));
  49         if (it == stations.end()) {
  50                 // create
  51                 const Id a = stations.size();
  52                 set<Time> s;
  53                 s.insert(time);
  54                 stations[station_name] = pair<Id, set<Time> >(a, s);
  55                 return a;
  56         } else {
  57                 pair<Id,set<Time> >& t = stations[station_name];
  58                 t._timeset.insert(time);
  59                 return t._id;
  60         }
  61 }
  62
  63 inline int time_in_minutes(string& s) {
  64         // h:mm hh:mm hhh:mm ...
  65         const int l = s.size();
  66         assert(s[l - 3] == ':');
  67         return atoi(s.substr(0, l - 3).c_str()) * HOUR + atoi(s.substr(l - 2, 2).c_str());
  68 }
  69
  70 void print_graph(Grafo& g) {
  71         forall (x, g) {
  72                 cout << "Hasta: " << x->_nodo._id << " a las " << (x->_nodo._time / 60) << ":" << (x->_nodo._time % 60) << endl;
  73                 forall (y, x->_ady) {
  74                         cout << "    desde " << y->dest._id
  75                                 << " a las " << (y->dest._time / 60) << ":" << (y->dest._time % 60)
  76                                 << " costo: " << (y->cost / 60) << ":" << (y->cost % 60) << endl;
  77                 }
  78         }
  79 }
  80
  81 #define INF     0x7fffffff
  82
  83 inline void dijkstra(Stations& stations, Grafo& graph, const string& origen, const string& destino) {
  84         const Id id_origen = stations[origen]._id;
  85         const Id id_destino = stations[destino]._id;
  86
  87         set<pair<Time, Nodo> > cola;
  88         map<Nodo, Time> distancia;
  89
  90         // inicializar distancias
  91         forall (st, stations) {
  92                 Id station_id = st->_info._id;
  93                 forall (t, st->_info._timeset) {
  94                         Nodo v(station_id, *t);
  95                         if (station_id == id_destino) {
  96                                 cola.insert(pair<Time,Nodo>(0, v));
  97                                 distancia[v] = 0;
  98                         } else {
  99                                 distancia[v] = INF;
 100                         }
 101                 }
 102         }
 103         while (!cola.empty()) {
 104                 // buscar el minimo
 105                 Time min_dist = cola.begin()->first;
 106
 107                 // borrarlo de la cola
 108                 Nodo min_node = cola.begin()->second;
 109                 cola.erase(cola.begin());
 110
 111                 // procesar min_node
 112                 forall (eje, graph[min_node]) {
 113                         const Time dist_nueva = min_dist + eje->cost;
 114                         const Time dist_actual = distancia[eje->dest];
 115                         if (dist_nueva < dist_actual) {
 116                                 if (dist_actual != INF) {
 117                                         cola.erase(cola.find(pair<Time,Nodo>(dist_actual, eje->dest)));
 118                                 }
 119                                 distancia[eje->dest] = dist_nueva;
 120                                 cola.insert(pair<Time,Nodo>(dist_nueva, eje->dest));
 121                         }
 122                 }
 123         }
 124
 125         list<pair<Time, Time> > salida;
 126         Time min_hora_llega = INF;
 127         forall (t, stations[origen]._timeset) {
 128                 Nodo v(id_origen, *t);
 129                 const Time hora_llega = *t + distancia[v] + DAY;
 130                 min_hora_llega = min(min_hora_llega, hora_llega);
 131         }
 132         dforall (t, stations[origen]._timeset) {
 133                 Nodo v(id_origen, *t);
 134                 const Time hora_sale = *t;
 135                 const Time hora_llega = *t + distancia[v];
 136                 if (hora_llega >= min_hora_llega) continue;
 137                 min_hora_llega = hora_llega;
 138                 salida.push_front(pair<Time, Time>(hora_sale, distancia[v]));
 139         }
 140         forall (res, salida) {
 141                 printf("%.2i:%.2i ", res->first / 60, res->first % 60);
 142                 printf("%i:%.2i\n", res->second / 60, res->second % 60);
 143         }
 144 }
 145
 146 #define add_edge(g, v1, v2, c) ((g)[(v1)].push_back((Edge){dest: (v2), cost: (c)}))
 147 int main() {
 148         int ncases;
 149         cin >> ncases;
 150
 151         forn (c, ncases) {
 152                 Stations stations;
 153                 Grafo graph;
 154
 155                 int num_trains;
 156                 cin >> num_trains;
 157
 158                 // read trains and stations
 159                 forn (t, num_trains) {
 160                         int num_stations;
 161                         cin >> num_stations;
 162
 163                         Nodo prev;
 164                         int time = 0;
 165                         forn (s, num_stations) {
 166                                 string time_str, station_name;
 167                                 cin >> time_str >> station_name;
 168
 169                                 const Time cost = time_in_minutes(time_str);
 170                                 time = (time + cost) % DAY;
 171                                 const Id station_id = register_station(stations, station_name, time);
 172
 173                                 const Nodo next(station_id, time);
 174                                 if (s != 0) {
 175                                         add_edge(graph, next, prev, cost);
 176                                 }
 177                                 prev = next;
 178                         }
 179                 }
 180
 181                 // complete the graph with the self edges for each station
 182                 forall (station, stations) {
 183                         const Id id = station->_info._id;
 184                         const set<Time>& timeset = station->_info._timeset;
 185                         if (timeset.size() == 1) continue;
 186                         forall (t1, timeset) {
 187                                 set<Time>::iterator t2 = t1;
 188                                 t2++;
 189                                 const Nodo v1(id, *t1);
 190                                 const Nodo v2(id, t2 == timeset.end() ? *timeset.begin() : *t2);
 191                                 Time cost = v2._time - v1._time;
 192                                 if (cost < 0) cost += DAY;
 193                                 add_edge(graph, v2, v1, cost);
 194                         }
 195                 }
 196
 197                 string origen, destino;
 198                 cin >> origen >> destino;
 199
 200                 dijkstra(stations, graph, origen, destino);
 201                 if (c != ncases - 1) {
 202                         cout << endl;
 203                 }
 204         }
 205         return 0;
 206 }
 207